#include <iostream>
#include <vector>

using namespace std;

int w[] = {8,6,4,2,5};  //物品重量
int v[] = {6,4,7,8,6};  //物品价值
int c = 12;             //背包容量
int n = sizeof(w) / sizeof(w[0]);   //物品个数

//dp[n][c] = 最大价值。也就是说在第i个物品对应着的背包容量，存储着当前最大价值
vector<vector<int>> dp(n + 1,vector<int>(c + 1,0));     //dp数组，存储最优子结构

int main()
{
    for(int i = 1;i <= n; i++)
    {
        for(int j = 1;j <= c;j++)
        {
            if(w[i - 1] > j)//遍历dp的第i个，对应w[]里是第i-1个
            {
                dp[i][j] = dp[i - 1][j];
            }
            else
            {
                dp[i][j] = std::max(v[i - 1] + dp[i - 1][j - w[i - 1]],dp[i - 1][j]);
            }
        }
    }

    for(int i = 0;i <= n;i++)
    {
        for(int j = 0;j <= c;j++)
        {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
}